/*
 * DFA routines
 * This file is #included by regexec.c.
 *
 * Copyright (c) 1998, 1999 Henry Spencer.  All rights reserved.
 *
 * Development of this software was funded, in part, by Cray Research Inc.,
 * UUNET Communications Services Inc., Sun Microsystems Inc., and Scriptics
 * Corporation, none of whom are responsible for the results.  The author
 * thanks all of them.
 *
 * Redistribution and use in source and binary forms -- with or without
 * modification -- are permitted for any purpose, provided that
 * redistributions in source form retain this entire copyright notice and
 * indicate the origin and nature of any modifications.
 *
 * I'd appreciate being given credit for this package in the documentation
 * of software which uses it, but that is not a requirement.
 *
 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES,
 * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
 * AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL
 * HENRY SPENCER BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
 * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
 * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 * src/backend/regex/rege_dfa.c
 *
 */

/* 
 * longest - 最长优先匹配引擎
 *
 * 成功时，返回匹配终点地址。没有匹配时返回 NULL。
 * 内部错误也返回 NULL，同时 v->err 被设置。
 */
static chr * longest(struct vars *v,
		struct dfa *fc_d,
		chr *fc_start,				/* 匹配应该开始的地方 */
		chr *fc_stop,				/* 匹配必须在此处或之前结束 */
		int *fc_hitstopp)			/* 记录是否命中 v->stop，如果非 NULL */
{
	chr		   *fc_cp;
	chr		   *fc_realstop = (fc_stop == v->stop) ? fc_stop : fc_stop + 1;
	color		fc_co;
	struct sset *fc_css;
	struct sset *fc_ss;
	chr		   *fc_post;
	int			fc_i;
	struct colormap *fc_cm = fc_d->cm;

	/* 防止“未初始化变量”警告 */
	if (fc_hitstopp != NULL)
		*fc_hitstopp = 0;

	/* 如果这是对已知字符串的反向引用，只需匹配该字符串 */
	if (fc_d->backno >= 0)
	{
		assert((size_t) fc_d->backno < v->nmatch);
		if (v->pmatch[fc_d->backno].rm_so >= 0)
		{
			fc_cp = dfa_backref(v, fc_d, fc_start, fc_start, fc_stop, false);
			if (fc_cp == v->stop && fc_stop == v->stop && fc_hitstopp != NULL)
				*fc_hitstopp = 1;
			return fc_cp;
		}
	}

	/* 匹配所有 NFA 的快速路径 */
	if (fc_d->cnfa->flags & MATCHALL)
	{
		size_t		fc_nchr = fc_stop - fc_start;
		size_t		fc_maxmatchall = fc_d->cnfa->maxmatchall;

		if (fc_nchr < fc_d->cnfa->minmatchall)
			return NULL;
		if (fc_maxmatchall == DUPINF)
		{
			if (fc_stop == v->stop && fc_hitstopp != NULL)
				*fc_hitstopp = 1;
		}
		else
		{
			if (fc_stop == v->stop && fc_nchr <= fc_maxmatchall + 1 && fc_hitstopp != NULL)
				*fc_hitstopp = 1;
			if (fc_nchr > fc_maxmatchall)
				return fc_start + fc_maxmatchall;
		}
		return fc_stop;
	}

	/* 初始化 */
	fc_css = initialize(v, fc_d, fc_start);
	if (fc_css == NULL)
		return NULL;
	fc_cp = fc_start;

	/* startup */
	FDEBUG(("+++ startup +++\n"));
	if (fc_cp == v->start)
	{
		fc_co = fc_d->cnfa->bos[(v->eflags & REG_NOTBOL) ? 0 : 1];
		FDEBUG(("color %ld\n", (long) fc_co));
	}
	else
	{
		fc_co = GETCOLOR(fc_cm, *(fc_cp - 1));
		FDEBUG(("char %c, color %ld\n", (char) *(fc_cp - 1), (long) fc_co));
	}
	fc_css = miss(v, fc_d, fc_css, fc_co, fc_cp, fc_start);
	if (fc_css == NULL)
		return NULL;
	fc_css->lastseen = fc_cp;

	/* 
	 * 这是主要的文本扫描循环。似乎值得拥有两个副本
	 * 以避免在此处进行 REG_FTRACE 测试的开销，即使在 REG_DEBUG
	 * 构建中，当你没有主动追踪时。
	 */
#ifdef REG_DEBUG
	if (v->eflags & REG_FTRACE)
	{
		while (fc_cp < fc_realstop)
		{
			FDEBUG(("+++ at c%d +++\n", (int) (fc_css - fc_d->ssets)));
			fc_co = GETCOLOR(fc_cm, *fc_cp);
			FDEBUG(("char %c, color %ld\n", (char) *fc_cp, (long) fc_co));
			fc_ss = fc_css->outs[fc_co];
			if (fc_ss == NULL)
			{
				fc_ss = miss(v, fc_d, fc_css, fc_co, fc_cp + 1, fc_start);
				if (fc_ss == NULL)
					break;		/* 注意突破 */
			}
			fc_cp++;
			fc_ss->lastseen = fc_cp;
			fc_css = fc_ss;
		}
	}
	else
#endif
	{
		while (fc_cp < fc_realstop)
		{
			fc_co = GETCOLOR(fc_cm, *fc_cp);
			fc_ss = fc_css->outs[fc_co];
			if (fc_ss == NULL)
			{
				fc_ss = miss(v, fc_d, fc_css, fc_co, fc_cp + 1, fc_start);
				if (fc_ss == NULL)
					break;		/* 注意突破 */
			}
			fc_cp++;
			fc_ss->lastseen = fc_cp;
			fc_css = fc_ss;
		}
	}

	if (ISERR())
		return NULL;

	/* shutdown */
	FDEBUG(("+++ shutdown at c%d +++\n", (int) (fc_css - fc_d->ssets)));
	if (fc_cp == v->stop && fc_stop == v->stop)
	{
		if (fc_hitstopp != NULL)
			*fc_hitstopp = 1;
		fc_co = fc_d->cnfa->eos[(v->eflags & REG_NOTEOL) ? 0 : 1];
		FDEBUG(("color %ld\n", (long) fc_co));
		fc_ss = miss(v, fc_d, fc_css, fc_co, fc_cp, fc_start);
		if (ISERR())
			return NULL;
		/* 特殊情况：匹配是否在行尾结束？ */
		if (fc_ss != NULL && (fc_ss->flags & POSTSTATE))
			return fc_cp;
		else if (fc_ss != NULL)
			fc_ss->lastseen = fc_cp;	/* 为了整洁 */
	}

	/* 找到最后一个匹配，如果有的话 */
	fc_post = fc_d->lastpost;
	for (fc_ss = fc_d->ssets, fc_i = fc_d->nssused; fc_i > 0; fc_ss++, fc_i--)
		if ((fc_ss->flags & POSTSTATE) && fc_post != fc_ss->lastseen &&
			(fc_post == NULL || fc_post < fc_ss->lastseen))
			fc_post = fc_ss->lastseen;
	if (fc_post != NULL)			/* 找到一个 */
		return fc_post - 1;

	return NULL;
}

/* 
 * shortest - 最短优先匹配引擎
 *
 * 成功时，返回匹配终点地址。没有匹配时返回 NULL。
 * 内部错误也返回 NULL，同时 v->err 被设置。
 */
static chr * shortest(struct vars *v,
		 struct dfa *fc_d,
		 chr *fc_start,			/* 匹配应该开始的地方 */
		 chr *fc_min,				/* 匹配必须在此处或之后结束 */
		 chr *fc_max,				/* 匹配必须在此处或之前结束 */
		 chr **fc_coldp,			/* 如果非 NULL，在此处存储冷启动指针 */
		 int *fc_hitstopp)			/* 记录是否命中 v->stop，如果非 NULL */
{
	chr		   *fc_cp;
	chr		   *fc_realmin = (fc_min == v->stop) ? fc_min : fc_min + 1;
	chr		   *fc_realmax = (fc_max == v->stop) ? fc_max : fc_max + 1;
	color		fc_co;
	struct sset *fc_css;
	struct sset *fc_ss;
	struct colormap *fc_cm = fc_d->cm;

	/* 防止“未初始化变量”警告 */
	if (fc_coldp != NULL)
		*fc_coldp = NULL;
	if (fc_hitstopp != NULL)
		*fc_hitstopp = 0;

	/* 如果这是对已知字符串的反向引用，只需匹配该字符串 */
	if (fc_d->backno >= 0)
	{
		assert((size_t) fc_d->backno < v->nmatch);
		if (v->pmatch[fc_d->backno].rm_so >= 0)
		{
			fc_cp = dfa_backref(v, fc_d, fc_start, fc_min, fc_max, true);
			if (fc_cp != NULL && fc_coldp != NULL)
				*fc_coldp = fc_start;
			/* 没有情况会设置 *hitstopp */
			return fc_cp;
		}
	}

	/* 匹配所有 NFA 的快速路径 */
	if (fc_d->cnfa->flags & MATCHALL)
	{
		size_t		fc_nchr = fc_min - fc_start;

		if (fc_d->cnfa->maxmatchall != DUPINF &&
			fc_nchr > fc_d->cnfa->maxmatchall)
			return NULL;
		if ((fc_max - fc_start) < fc_d->cnfa->minmatchall)
			return NULL;
		if (fc_nchr < fc_d->cnfa->minmatchall)
			fc_min = fc_start + fc_d->cnfa->minmatchall;
		if (fc_coldp != NULL)
			*fc_coldp = fc_start;
		/* 没有情况会设置 *hitstopp */
		return fc_min;
	}

	/* 初始化 */
	fc_css = initialize(v, fc_d, fc_start);
	if (fc_css == NULL)
		return NULL;
	fc_cp = fc_start;

	/* startup */
	FDEBUG(("--- startup ---\n"));
	if (fc_cp == v->start)
	{
		fc_co = fc_d->cnfa->bos[(v->eflags & REG_NOTBOL) ? 0 : 1];
		FDEBUG(("color %ld\n", (long) fc_co));
	}
	else
	{
		fc_co = GETCOLOR(fc_cm, *(fc_cp - 1));
		FDEBUG(("char %c, color %ld\n", (char) *(fc_cp - 1), (long) fc_co));
	}
	fc_css = miss(v, fc_d, fc_css, fc_co, fc_cp, fc_start);
	if (fc_css == NULL)
		return NULL;
	fc_css->lastseen = fc_cp;
	fc_ss = fc_css;

	/* 
	 * 这是主要的文本扫描循环。似乎值得拥有两个副本
	 * 以避免在此处进行 REG_FTRACE 测试的开销，即使在 REG_DEBUG
	 * 构建中，当你没有主动追踪时。
	 */
#ifdef REG_DEBUG
	if (v->eflags & REG_FTRACE)
	{
		while (fc_cp < fc_realmax)
		{
			FDEBUG(("--- at c%d ---\n", (int) (fc_css - fc_d->ssets)));
			fc_co = GETCOLOR(fc_cm, *fc_cp);
			FDEBUG(("char %c, color %ld\n", (char) *fc_cp, (long) fc_co));
			fc_ss = fc_css->outs[fc_co];
			if (fc_ss == NULL)
			{
				fc_ss = miss(v, fc_d, fc_css, fc_co, fc_cp + 1, fc_start);
				if (fc_ss == NULL)
					break;		/* 注意突破 */
			}
			fc_cp++;
			fc_ss->lastseen = fc_cp;
			fc_css = fc_ss;
			if ((fc_ss->flags & POSTSTATE) && fc_cp >= fc_realmin)
				break;			/* 注意突破 */
		}
	}
	else
#endif
	{
		while (fc_cp < fc_realmax)
		{
			fc_co = GETCOLOR(fc_cm, *fc_cp);
			fc_ss = fc_css->outs[fc_co];
			if (fc_ss == NULL)
			{
				fc_ss = miss(v, fc_d, fc_css, fc_co, fc_cp + 1, fc_start);
				if (fc_ss == NULL)
					break;		/* 注意突破 */
			}
			fc_cp++;
			fc_ss->lastseen = fc_cp;
			fc_css = fc_ss;
			if ((fc_ss->flags & POSTSTATE) && fc_cp >= fc_realmin)
				break;			/* 注意突破 */
		}
	}

	if (fc_ss == NULL)
		return NULL;

	if (fc_coldp != NULL)			/* 如果有，报告最后一个无进展状态设置 */
		*fc_coldp = lastcold(v, fc_d);

	if ((fc_ss->flags & POSTSTATE) && fc_cp > fc_min)
	{
		assert(fc_cp >= fc_realmin);
		fc_cp--;
	}
	else if (fc_cp == v->stop && fc_max == v->stop)
	{
		fc_co = fc_d->cnfa->eos[(v->eflags & REG_NOTEOL) ? 0 : 1];
		FDEBUG(("color %ld\n", (long) fc_co));
		fc_ss = miss(v, fc_d, fc_css, fc_co, fc_cp, fc_start);
		/* 匹配可能在行尾结束 */
		if ((fc_ss == NULL || !(fc_ss->flags & POSTSTATE)) && fc_hitstopp != NULL)
			*fc_hitstopp = 1;
	}

	if (fc_ss == NULL || !(fc_ss->flags & POSTSTATE))
		return NULL;

	return fc_cp;
}

/*
 * matchuntil - 增量匹配引擎
 *
 * 这用于与搜索风格的 NFA 一起使用（也就是说，模式已知会表现得好像它有一个前导 .*）。我们确定是否存在从 v->start 开始到 probe 结束的匹配。多个调用只需 O(N) 时间而不是 O(N^2)，只要 probe 值是非递减的。*lastcss 和 *lastcp 必须在开始一系列调用之前初始化为 NULL。
 *
 * 如果存在匹配，则返回 1，若不存在，则返回 0。
 * 内部错误也返回 0，并设置 v->err。
 */
static int matchuntil(struct vars *v,
		   struct dfa *fc_d,
		   chr *fc_probe,			/* 我们想知道匹配是否在这里结束 */
		   struct sset **fc_lastcss,	/* 跨调用的状态存储 */
		   chr **fc_lastcp)		/* 跨调用的状态存储 */
{
	chr		   *fc_cp = *fc_lastcp;
	color		fc_co;
	struct sset *fc_css = *fc_lastcss;
	struct sset *fc_ss;
	struct colormap *fc_cm = fc_d->cm;

	/* 匹配所有 NFA 的快速路径 */
	if (fc_d->cnfa->flags & MATCHALL)
	{
		size_t		fc_nchr = fc_probe - v->start;

		if (fc_nchr < fc_d->cnfa->minmatchall)
			return 0;
		/* maxmatchall 将始终是无限大的，参见 makesearch() */
		assert(fc_d->cnfa->maxmatchall == DUPINF);
		return 1;
	}

	/* 初始化和启动，或在必要时重新启动 */
	if (fc_cp == NULL || fc_cp > fc_probe)
	{
		fc_cp = v->start;
		fc_css = initialize(v, fc_d, fc_cp);
		if (fc_css == NULL)
			return 0;

		FDEBUG((">>> startup >>>\n"));
		fc_co = fc_d->cnfa->bos[(v->eflags & REG_NOTBOL) ? 0 : 1];
		FDEBUG(("color %ld\n", (long) fc_co));

		fc_css = miss(v, fc_d, fc_css, fc_co, fc_cp, v->start);
		if (fc_css == NULL)
			return 0;
		fc_css->lastseen = fc_cp;
	}
	else if (fc_css == NULL)
	{
		/* 我们之前发现没有匹配可能超出 *lastcp */
		return 0;
	}
	fc_ss = fc_css;

	/* 
	 * 这是主要的文本扫描循环。似乎值得拥有两个副本
	 * 以避免在此处进行 REG_FTRACE 测试的开销，即使在 REG_DEBUG
	 * 构建中，当你没有主动追踪时。
	 */
#ifdef REG_DEBUG
	if (v->eflags & REG_FTRACE)
	{
		while (fc_cp < fc_probe)
		{
			FDEBUG((">>> at c%d >>>\n", (int) (fc_css - fc_d->ssets)));
			fc_co = GETCOLOR(fc_cm, *fc_cp);
			FDEBUG(("char %c, color %ld\n", (char) *fc_cp, (long) fc_co));
			fc_ss = fc_css->outs[fc_co];
			if (fc_ss == NULL)
			{
				fc_ss = miss(v, fc_d, fc_css, fc_co, fc_cp + 1, v->start);
				if (fc_ss == NULL)
					break;		/* 注意突破 */
			}
			fc_cp++;
			fc_ss->lastseen = fc_cp;
			fc_css = fc_ss;
		}
	}
	else
#endif
	{
		while (fc_cp < fc_probe)
		{
			fc_co = GETCOLOR(fc_cm, *fc_cp);
			fc_ss = fc_css->outs[fc_co];
			if (fc_ss == NULL)
			{
				fc_ss = miss(v, fc_d, fc_css, fc_co, fc_cp + 1, v->start);
				if (fc_ss == NULL)
					break;		/* 注意突破 */
			}
			fc_cp++;
			fc_ss->lastseen = fc_cp;
			fc_css = fc_ss;
		}
	}

	*fc_lastcss = fc_ss;
	*fc_lastcp = fc_cp;

	if (fc_ss == NULL)
		return 0;				/* 不可能的匹配或内部错误 */

	/* 我们需要处理一个字符或 EOS 符号，以检查匹配 */
	if (fc_cp < v->stop)
	{
		FDEBUG((">>> at c%d >>>\n", (int) (fc_css - fc_d->ssets)));
		fc_co = GETCOLOR(fc_cm, *fc_cp);
		FDEBUG(("char %c, color %ld\n", (char) *fc_cp, (long) fc_co));
		fc_ss = fc_css->outs[fc_co];
		if (fc_ss == NULL)
			fc_ss = miss(v, fc_d, fc_css, fc_co, fc_cp + 1, v->start);
	}
	else
	{
		assert(fc_cp == v->stop);
		fc_co = fc_d->cnfa->eos[(v->eflags & REG_NOTEOL) ? 0 : 1];
		FDEBUG(("color %ld\n", (long) fc_co));
		fc_ss = miss(v, fc_d, fc_css, fc_co, fc_cp, v->start);
	}

	if (fc_ss == NULL || !(fc_ss->flags & POSTSTATE))
		return 0;

	return 1;
}

/*
 * dfa_backref - 查找已知回溯字符串的最佳匹配长度
 *
 * 当回溯的引用者已经可用时，我们可以提供一个确切的答案，而不会像运行回溯节点的 NFA 那样繁琐。
 *
 * 返回最长或最短有效重复匹配的匹配端点，
 * 如果没有有效匹配，则返回 NULL。
 *
 * 应与 cbrdissect() 同步，尽管那个的任务是检查与字符串预定部分的匹配。
 */
static chr * dfa_backref(struct vars *v,
			struct dfa *fc_d,
			chr *fc_start,			/* 匹配应该开始的地方 */
			chr *fc_min,			/* 匹配必须在此处或之后结束 */
			chr *fc_max,			/* 匹配必须在此处或之前结束 */
			bool fc_shortest)
{
	int			fc_n = fc_d->backno;
	int			fc_backmin = fc_d->backmin;
	int			fc_backmax = fc_d->backmax;
	size_t		fc_numreps;
	size_t		fc_minreps;
	size_t		fc_maxreps;
	size_t		fc_brlen;
	chr		   *fc_brstring;
	chr		   *fc_p;

	/* 获取回溯字符串（调用者应该检查过这个） */
	if (v->pmatch[fc_n].rm_so == -1)
		return NULL;
	fc_brstring = v->start + v->pmatch[fc_n].rm_so;
	fc_brlen = v->pmatch[fc_n].rm_eo - v->pmatch[fc_n].rm_so;

	/* 特殊情况处理零长度回溯，以避免除以零 */
	if (fc_brlen == 0)
	{
		/*
		 * 只匹配零长度字符串，但可以认为存在任何数量的重复
		 */
		if (fc_min == fc_start && fc_backmin <= fc_backmax)
			return fc_start;
		return NULL;
	}

	/*
	 * 将最小值和最大值转换为可能的回溯字符串重复次数，适当四舍五入
	 */
	if (fc_min <= fc_start)
		fc_minreps = 0;
	else
		fc_minreps = (fc_min - fc_start - 1) / fc_brlen + 1;
	fc_maxreps = (fc_max - fc_start) / fc_brlen;

	/* 应用限制，然后查看是否有任何允许的匹配长度 */
	if (fc_minreps < fc_backmin)
		fc_minreps = fc_backmin;
	if (fc_backmax != DUPINF && fc_maxreps > fc_backmax)
		fc_maxreps = fc_backmax;
	if (fc_maxreps < fc_minreps)
		return NULL;

	/* 如果零重复匹配有效且受欢迎，则快速退出 */
	if (fc_shortest && fc_minreps == 0)
		return fc_start;

	/* 好吧，比较实际的字符串内容 */
	fc_p = fc_start;
	fc_numreps = 0;
	while (fc_numreps < fc_maxreps)
	{
		if ((*v->g->compare) (fc_brstring, fc_p, fc_brlen) != 0)
			break;
		fc_p += fc_brlen;
		fc_numreps++;
		if (fc_shortest && fc_numreps >= fc_minreps)
			break;
	}

	if (fc_numreps >= fc_minreps)
		return fc_p;
	return NULL;
}

/*
 * lastcold - 确定没有进展时的最后一点
 */
static chr *					/* 端点或 NULL */
lastcold(struct vars *v,
		 struct dfa *fc_d)
{
	struct sset *fc_ss;
	chr		   *nopr;
	int			fc_i;

	nopr = fc_d->lastnopr;
	if (nopr == NULL)
		nopr = v->start;
	for (fc_ss = fc_d->ssets, fc_i = fc_d->nssused; fc_i > 0; fc_ss++, fc_i--)
		if ((fc_ss->flags & NOPROGRESS) && nopr < fc_ss->lastseen)
			nopr = fc_ss->lastseen;
	return nopr;
}

/*
 * newdfa - 设置一个新的 DFA
 *
 * 失败时返回 NULL（并设置 v->err）。
 */
static struct dfa * newdfa(struct vars *v,
	   struct cnfa *fc_cnfa,
	   struct colormap *fc_cm,
	   struct smalldfa *fc_sml)	/* 预分配空间，可能为 NULL */
{
	struct dfa *fc_d;
#ifdef FDD //cppcheck，必须先断言 cnfa 为 null 
	size_t		fc_nss = 0;
	int			fc_wordsper = 0;

	bool		fc_ismalloced = false;

	assert(fc_cnfa != NULL && fc_cnfa->nstates != 0);

	fc_nss =  fc_cnfa->nstates * 2;
	fc_wordsper =  (fc_cnfa->nstates + UBITS - 1) / UBITS;
	
#else
	size_t		fc_nss = fc_cnfa->nstates * 2;
	int			fc_wordsper = (fc_cnfa->nstates + UBITS - 1) / UBITS;
	bool		fc_ismalloced = false;

	assert(fc_cnfa != NULL && fc_cnfa->nstates != 0);

#endif
	if (fc_nss <= FEWSTATES && fc_cnfa->ncolors <= FEWCOLORS)
	{
		assert(fc_wordsper == 1);
		if (fc_sml == NULL)
		{
			fc_sml = (struct smalldfa *) MALLOC(sizeof(struct smalldfa));
			if (fc_sml == NULL)
			{
				ERR(REG_ESPACE);
				return NULL;
			}
			fc_ismalloced = true;
		}
		fc_d = &fc_sml->dfa;
		fc_d->ssets = fc_sml->ssets;
		fc_d->statesarea = fc_sml->statesarea;
		fc_d->work = &fc_d->statesarea[fc_nss];
		fc_d->outsarea = fc_sml->outsarea;
		fc_d->incarea = fc_sml->incarea;
		fc_d->ismalloced = fc_ismalloced;
		fc_d->arraysmalloced = false;	/* 反正不是单独分配的 */
	}
	else
	{
		fc_d = (struct dfa *) MALLOC(sizeof(struct dfa));
		if (fc_d == NULL)
		{
			ERR(REG_ESPACE);
			return NULL;
		}
		fc_d->ssets = (struct sset *) MALLOC(fc_nss * sizeof(struct sset));
		fc_d->statesarea = (unsigned *) MALLOC((fc_nss + WORK) * fc_wordsper *
											sizeof(unsigned));
		fc_d->work = &fc_d->statesarea[fc_nss * fc_wordsper];
		fc_d->outsarea = (struct sset **) MALLOC(fc_nss * fc_cnfa->ncolors *
											  sizeof(struct sset *));
		fc_d->incarea = (struct arcp *) MALLOC(fc_nss * fc_cnfa->ncolors *
											sizeof(struct arcp));
		fc_d->ismalloced = true;
		fc_d->arraysmalloced = true;
		/* 现在 freedfa() 将正常工作 */
		if (fc_d->ssets == NULL || fc_d->statesarea == NULL ||
			fc_d->outsarea == NULL || fc_d->incarea == NULL)
		{
			freedfa(fc_d);
			ERR(REG_ESPACE);
			return NULL;
		}
	}

	fc_d->nssets = (v->eflags & REG_SMALL) ? 7 : fc_nss;
	fc_d->nssused = 0;
	fc_d->nstates = fc_cnfa->nstates;
	fc_d->ncolors = fc_cnfa->ncolors;
	fc_d->wordsper = fc_wordsper;
	fc_d->cnfa = fc_cnfa;
	fc_d->cm = fc_cm;
	fc_d->lastpost = NULL;
	fc_d->lastnopr = NULL;
	fc_d->search = fc_d->ssets;
	fc_d->backno = -1;				/* 可以由调用者设置 */
	fc_d->backmin = fc_d->backmax = 0;

	/* sset 字段的初始化根据需要进行 */

	return fc_d;
}

/*
 * freedfa - 释放 DFA
 */
static void freedfa(struct dfa *fc_d)
{
	if (fc_d->arraysmalloced)
	{
		if (fc_d->ssets != NULL)
			FREE(fc_d->ssets);
		if (fc_d->statesarea != NULL)
			FREE(fc_d->statesarea);
		if (fc_d->outsarea != NULL)
			FREE(fc_d->outsarea);
		if (fc_d->incarea != NULL)
			FREE(fc_d->incarea);
	}

	if (fc_d->ismalloced)
		FREE(fc_d);
}

/*
 * hash - 为比特向量构造哈希代码
 *
 * 可能有更好的方法，但它们更昂贵。
 */
static unsigned hash(unsigned *fc_uv,
	 int fc_n)
{
	int			fc_i;
	unsigned	fc_h;

	fc_h = 0;
	for (fc_i = 0; fc_i < fc_n; fc_i++)
		fc_h ^= fc_uv[fc_i];
	return fc_h;
}

/*
 * initialize - 手动制作缓存条目的启动，或者做好准备
 */
static struct sset * initialize(struct vars *v,
		   struct dfa *fc_d,
		   chr *fc_start)
{
	struct sset *fc_ss;
	int			fc_i;

	/* 前一个仍然存在吗？ */
	if (fc_d->nssused > 0 && (fc_d->ssets[0].flags & STARTER))
		fc_ss = &fc_d->ssets[0];
	else
	{							/* 不，可以（重新）构建它 */
		fc_ss = getvacant(v, fc_d, fc_start, fc_start);
		if (fc_ss == NULL)
			return NULL;
		for (fc_i = 0; fc_i < fc_d->wordsper; fc_i++)
			fc_ss->states[fc_i] = 0;
		BSET(fc_ss->states, fc_d->cnfa->pre);
		fc_ss->hash = HASH(fc_ss->states, fc_d->wordsper);
		assert(fc_d->cnfa->pre != fc_d->cnfa->post);
		fc_ss->flags = STARTER | LOCKED | NOPROGRESS;
		/* 最后看到的处理在下面 */
	}

	for (fc_i = 0; fc_i < fc_d->nssused; fc_i++)
		fc_d->ssets[fc_i].lastseen = NULL;
	fc_ss->lastseen = fc_start;		/* 可能不真实，但无害 */
	fc_d->lastpost = NULL;
	fc_d->lastnopr = NULL;
	return fc_ss;
}

/*
 * miss - 处理状态集缓存未命中
 *
 * css 是当前的状态集，co 是当前输入字符的颜色，
 * cp 指向之后的字符（在这里我们可能需要测试
 * LACONs）。start 不影响匹配行为，但对于 pickss 的
 * 关于替换哪个状态集缓存条目的启发式方法是必需的。
 *
 * 通常情况下，返回下一个状态集的地址（在消费输入字符后
 * 有效的那个）。如果没有有效的 NFA 状态，则返回 NULL， 
 * 即我们遇到了确定的匹配失败。
 * 内部错误也返回 NULL，并设置 v->err。
 */
static struct sset * miss(struct vars *v,
	 struct dfa *fc_d,
	 struct sset *fc_css,
	 color fc_co,
	 chr *fc_cp,					/* next chr */
	 chr *fc_start)				/* 尝试开始的地方 */
{
	struct cnfa *fc_cnfa = fc_d->cnfa;
	int			fc_i;
	unsigned	fc_h;
	struct carc *fc_ca;
	struct sset *fc_p;
	int			fc_ispseudocolor;
	int			fc_ispost;
	int			fc_noprogress;
	int			fc_gotstate;
	int			fc_dolacons;
	int			fc_sawlacons;

	/* 为了方便，即使可能不是未命中，我们也可以被调用 */
	if (fc_css->outs[fc_co] != NULL)
	{
		FDEBUG(("hit\n"));
		return fc_css->outs[fc_co];
	}
	FDEBUG(("miss\n"));

	/*
	 * 在内部文本搜索循环中检查操作取消似乎
	 * 显得过于昂贵。作为妥协，在缓存未命中时进行检查。
	 */
	if (CANCEL_REQUESTED(v->re))
	{
		ERR(REG_CANCEL);
		return NULL;
	}

	/*
	 * 在消费 co 字符后，我们会最终进入哪一组状态？
	 * 我们首先考虑消耗字符的 PLAIN 弧，然后查看
	 * 消耗之后可以遍历哪些 LACON 弧。
	 */
	for (fc_i = 0; fc_i < fc_d->wordsper; fc_i++)
		fc_d->work[fc_i] = 0;			/* 在 d->work 中构建新的状态集位图 */
	fc_ispseudocolor = fc_d->cm->cd[fc_co].flags & PSEUDO;
	fc_ispost = 0;
	fc_noprogress = 1;
	fc_gotstate = 0;
	for (fc_i = 0; fc_i < fc_d->nstates; fc_i++)
		if (ISBSET(fc_css->states, fc_i))
			for (fc_ca = fc_cnfa->states[fc_i]; fc_ca->co != COLORLESS; fc_ca++)
				if (fc_ca->co == fc_co ||
					(fc_ca->co == RAINBOW && !fc_ispseudocolor))
				{
					BSET(fc_d->work, fc_ca->to);
					fc_gotstate = 1;
					if (fc_ca->to == fc_cnfa->post)
						fc_ispost = 1;
					if (!(fc_cnfa->stflags[fc_ca->to] & CNFA_NOPROGRESS))
						fc_noprogress = 0;
					FDEBUG(("%d -> %d\n", fc_i, fc_ca->to));
				}
	if (!fc_gotstate)
		return NULL;			/* 字符无法到达任何新状态 */
	fc_dolacons = (fc_cnfa->flags & HASLACONS);
	fc_sawlacons = 0;
	/* 外循环处理 LACON 状态可达的传递闭包 */
	while (fc_dolacons)
	{
		fc_dolacons = 0;
		for (fc_i = 0; fc_i < fc_d->nstates; fc_i++)
			if (ISBSET(fc_d->work, fc_i))
				for (fc_ca = fc_cnfa->states[fc_i]; fc_ca->co != COLORLESS; fc_ca++)
				{
					if (fc_ca->co < fc_cnfa->ncolors)
						continue;	/* 不是 LACON 弧 */
					if (ISBSET(fc_d->work, fc_ca->to))
						continue;	/* 弧本身就会是个无操作 */
					fc_sawlacons = 1;	/* 这个 LACON 影响我们的结果 */
					if (!lacon(v, fc_cnfa, fc_cp, fc_ca->co))
					{
						if (ISERR())
							return NULL;
						continue;	/* LACON 弧无法遍历 */
					}
					if (ISERR())
						return NULL;
					BSET(fc_d->work, fc_ca->to);
					fc_dolacons = 1;
					if (fc_ca->to == fc_cnfa->post)
						fc_ispost = 1;
					if (!(fc_cnfa->stflags[fc_ca->to] & CNFA_NOPROGRESS))
						fc_noprogress = 0;
					FDEBUG(("%d :> %d\n", fc_i, fc_ca->to));
				}
	}
	fc_h = HASH(fc_d->work, fc_d->wordsper);

	/* 这个状态集已经在缓存中吗？ */
	for (fc_p = fc_d->ssets, fc_i = fc_d->nssused; fc_i > 0; fc_p++, fc_i--)
		if (HIT(fc_h, fc_d->work, fc_p, fc_d->wordsper))
		{
			FDEBUG(("cached c%d\n", (int) (fc_p - fc_d->ssets)));
			break;				/* 注意突破 */
		}
	if (fc_i == 0)
	{							/* 不，需要一个新的缓存条目 */
		fc_p = getvacant(v, fc_d, fc_cp, fc_start);
		if (fc_p == NULL)
			return NULL;
		assert(fc_p != fc_css);
		for (fc_i = 0; fc_i < fc_d->wordsper; fc_i++)
			fc_p->states[fc_i] = fc_d->work[fc_i];
		fc_p->hash = fc_h;
		fc_p->flags = (fc_ispost) ? POSTSTATE : 0;
		if (fc_noprogress)
			fc_p->flags |= NOPROGRESS;
		/* 最后看到的由调用者处理 */
	}

	/*
	 * 将新的状态集链接到旧的，除非 LACON 影响了结果，
	 * 在这种情况下我们不创建链接。这会迫使未来跨越
	 * 这条相同的弧（相同的先前状态集和字符颜色）的转移
	 * 再次经过 miss()，以便我们可以重新检查 LACON(s)，
	 * 这些 LACON 可能会或可能不会通过，因为上下文
	 * 会有所不同。
	 */
	if (!fc_sawlacons)
	{
		FDEBUG(("c%d[%d]->c%d\n",
				(int) (fc_css - fc_d->ssets), fc_co, (int) (fc_p - fc_d->ssets)));
		fc_css->outs[fc_co] = fc_p;
		fc_css->inchain[fc_co] = fc_p->ins;
		fc_p->ins.ss = fc_css;
		fc_p->ins.co = fc_co;
	}
	return fc_p;
}

/*
 * lacon - miss() 的查找约束检查器
 */
static int						/* 谓词：约束满足吗？ */
lacon(struct vars *v,
	  struct cnfa *pcnfa,		/* 父 cnfa */
	  chr *fc_cp,
	  color fc_co)					/* 查找约束的“颜色” */
{
	int			fc_n;
	struct subre *fc_sub;
	struct dfa *fc_d;
	chr		   *fc_end;
	int			fc_satisfied;

	/* 由于这是递归的，它可能导致堆栈溢出 */
	if (STACK_TOO_DEEP(v->re))
	{
		ERR(REG_ETOOBIG);
		return 0;
	}

	fc_n = fc_co - pcnfa->ncolors;
	assert(fc_n > 0 && fc_n < v->g->nlacons && v->g->lacons != NULL);
	FDEBUG(("=== testing lacon %d\n", fc_n));
	fc_sub = &v->g->lacons[fc_n];
	fc_d = getladfa(v, fc_n);
	if (fc_d == NULL)
		return 0;
	if (LATYPE_IS_AHEAD(fc_sub->latype))
	{
		/* 以前在这里使用 longest()，但 shortest() 可能便宜得多 */
		fc_end = shortest(v, fc_d, fc_cp, fc_cp, v->stop,
					   (chr **) NULL, (int *) NULL);
		fc_satisfied = LATYPE_IS_POS(fc_sub->latype) ? (fc_end != NULL) : (fc_end == NULL);
	}
	else
	{
		/*
		 * 为了避免在 N 字符串中反复测试一个回溯约束时执行 O(N^2) 的工作，
		 * 我们使用 matchuntil()，它可以在调用之间缓存 DFA 状态。
		 * 我们只需要在探测点下降时重新启动，这种情况并不常见。
		 * 我们使用的 NFA 是一个搜索 NFA，因此它不介意在名义匹配之前
		 * 进行扫描。
		 */
		fc_satisfied = matchuntil(v, fc_d, fc_cp, &v->lblastcss[fc_n], &v->lblastcp[fc_n]);
		if (!LATYPE_IS_POS(fc_sub->latype))
			fc_satisfied = !fc_satisfied;
	}
	FDEBUG(("=== lacon %d satisfied %d\n", fc_n, fc_satisfied));
	return fc_satisfied;
}

/*
 * getvacant - 获取一个空闲状态集
 *
 * 此例程清除 inarcs 和 outarcs，但不清除状态集的内部内容——
 * 这由调用者负责。
 */
static struct sset * getvacant(struct vars *v,
		  struct dfa *fc_d,
		  chr *fc_cp,
		  chr *fc_start)
{
	int			fc_i;
	struct sset *fc_ss;
	struct sset *fc_p;
	struct arcp fc_ap;
	color		fc_co;

	fc_ss = pickss(v, fc_d, fc_cp, fc_start);
	if (fc_ss == NULL)
		return NULL;
	assert(!(fc_ss->flags & LOCKED));

	/* 清除其 inarcs，包括自引用的那些 */
	fc_ap = fc_ss->ins;
	while ((fc_p = fc_ap.ss) != NULL)
	{
		fc_co = fc_ap.co;
		FDEBUG(("zapping c%d's %ld outarc\n", (int) (fc_p - fc_d->ssets), (long) fc_co));
		fc_p->outs[fc_co] = NULL;
		fc_ap = fc_p->inchain[fc_co];
		fc_p->inchain[fc_co].ss = NULL;	/* paranoia */
	}
	fc_ss->ins.ss = NULL;

	/* 将其从其 outarcs 到达的 ssets 的 inarc 链中移除 */
	for (fc_i = 0; fc_i < fc_d->ncolors; fc_i++)
	{
		fc_p = fc_ss->outs[fc_i];
		assert(fc_p != fc_ss);		/* 不是自引用的 */
		if (fc_p == NULL)
			continue;			/* 继续注意 */
		FDEBUG(("del outarc %d from c%d's in chn\n", fc_i, (int) (fc_p - fc_d->ssets)));
		if (fc_p->ins.ss == fc_ss && fc_p->ins.co == fc_i)
			fc_p->ins = fc_ss->inchain[fc_i];
		else
		{
			struct arcp lastap = {NULL, 0};

			assert(fc_p->ins.ss != NULL);
			for (fc_ap = fc_p->ins; fc_ap.ss != NULL &&
				 !(fc_ap.ss == fc_ss && fc_ap.co == fc_i);
				 fc_ap = fc_ap.ss->inchain[fc_ap.co])
				lastap = fc_ap;
			assert(fc_ap.ss != NULL);
			lastap.ss->inchain[lastap.co] = fc_ss->inchain[fc_i];
		}
		fc_ss->outs[fc_i] = NULL;
		fc_ss->inchain[fc_i].ss = NULL;
	}

	/*如果 ss 是成功状态，可能需要记住位置*/
	if ((fc_ss->flags & POSTSTATE) && fc_ss->lastseen != fc_d->lastpost &&
		(fc_d->lastpost == NULL || fc_d->lastpost < fc_ss->lastseen))
		fc_d->lastpost = fc_ss->lastseen;

	/*同样适用于无进展状态*/
	if ((fc_ss->flags & NOPROGRESS) && fc_ss->lastseen != fc_d->lastnopr &&
		(fc_d->lastnopr == NULL || fc_d->lastnopr < fc_ss->lastseen))
		fc_d->lastnopr = fc_ss->lastseen;

	return fc_ss;
}

/*
 * pickss - 选择下一个要使用的状态集
*/
static struct sset * pickss(struct vars *v,
	   struct dfa *fc_d,
	   chr *fc_cp,
	   chr *fc_start)
{
	int			fc_i;
	struct sset *fc_ss;
	struct sset *fc_end;
	chr		   *fc_ancient;

	/*缓存不满的情况下的简化处理*/
	if (fc_d->nssused < fc_d->nssets)
	{
		fc_i = fc_d->nssused;
		fc_d->nssused++;
		fc_ss = &fc_d->ssets[fc_i];
		FDEBUG(("new c%d\n", fc_i));
		/*设置内部结构*/
		fc_ss->states = &fc_d->statesarea[fc_i * fc_d->wordsper];
		fc_ss->flags = 0;
		fc_ss->ins.ss = NULL;
		fc_ss->ins.co = WHITE;		/*给它一些值*/
		fc_ss->outs = &fc_d->outsarea[fc_i * fc_d->ncolors];
		fc_ss->inchain = &fc_d->incarea[fc_i * fc_d->ncolors];
		for (fc_i = 0; fc_i < fc_d->ncolors; fc_i++)
		{
			fc_ss->outs[fc_i] = NULL;
			fc_ss->inchain[fc_i].ss = NULL;
		}
		return fc_ss;
	}

	/*寻找最古老的，或者说足够古老的*/
	if (fc_cp - fc_start > fc_d->nssets * 2 / 3) /*最古老的33%是可支配的*/
		fc_ancient = fc_cp - fc_d->nssets * 2 / 3;
	else
		fc_ancient = fc_start;
	for (fc_ss = fc_d->search, fc_end = &fc_d->ssets[fc_d->nssets]; fc_ss < fc_end; fc_ss++)
		if ((fc_ss->lastseen == NULL || fc_ss->lastseen < fc_ancient) &&
			!(fc_ss->flags & LOCKED))
		{
			fc_d->search = fc_ss + 1;
			FDEBUG(("replacing c%d\n", (int) (fc_ss - fc_d->ssets)));
			return fc_ss;
		}
	for (fc_ss = fc_d->ssets, fc_end = fc_d->search; fc_ss < fc_end; fc_ss++)
		if ((fc_ss->lastseen == NULL || fc_ss->lastseen < fc_ancient) &&
			!(fc_ss->flags & LOCKED))
		{
			fc_d->search = fc_ss + 1;
			FDEBUG(("replacing c%d\n", (int) (fc_ss - fc_d->ssets)));
			return fc_ss;
		}

	/*没有人够老？！ -- 这真的有问题*/
	FDEBUG(("cannot find victim to replace!\n"));
	ERR(REG_ASSERT);
	return NULL;
}
